|
| creator |
Baumann, Thomas
| | date |
2008
| | | | description |
37 pages
| |
Seit den 1960er Jahren befindet sich die Dot-Depth Hierarchie von
Brzozowski und Cohen im Zentrum der Erforschung sternfreier
regulärer Sprachen. Sie bildet in diesen eine strikte Hierarchie,
deren Vereinigung gerade die sternfreien Sprachen ergibt und die bis
zum heutigen Tage trotz einiger erstaunlicher Teilresultate nur auf
den untersten Ebenen vollständig verstanden wird.
Die vorliegende Arbeit befasst sich mit einem Resultat von Straubing
aus dem Jahre 1988, das die Entscheidbarkeit der zweiten Stufe
dieser Hierarchie für Sprachen mit maximal zwei Erzeugern
nachweist. Insbesondere wird dieses Resultat im Licht neuerer
Erkenntnisse der algebraischen Sprachentheorie betrachtet und eine
notwendige Bedingung für das Enthaltensein in einer bestimmten
Klasse von Monoiden erarbeitet. Abschließend wird diese verwendet
um einen neuen Gegenbeweis einer Vermutung, über die Struktur der
zweiten Stufe von Brzozowskis Hierarchie, aus dem Jahre 2001 zu
widerlegen.
| | format |
application/pdf
| | 328080 Bytes | |